package com.cskaoyan.javase.recursion._1basic;

/**
 * 递归的思想
 * 案例： 求n的阶乘
 * n! = n * (n-1) * (n-2) * ... * 1;
 * 用循环求解时，主要是找到能够循环执行的语句，找到循环体
 * 而在使用递归的时候，必须找到递归体和递归的出口
 * 首先要找递归体，递归体是方法调用自身，所以和方法应该是一样的规则，或者换句话说，只是把方法给分解了
 * n! = n * （n-1）!
 * (n-1)! = (n-1) * (n-2)!
 * ...
 * 2! = 2 * 1!
 * 1! = 1
 * 假如n的阶乘是f(n),那么f(n) = n * f(n-1)
 * 递归体: f(n) = n * f(n-1)
 * 递归的出口: f(1) = 1
 *
 * 递归的思想就是分解问题的思想:
 * 1. 把一个复杂的大规模的问题，分解成若干相似的小规模的子问题。(递归体)
 * 2. 当子问题规模足够小的时候，就可以直接得到小规模问题的解。 (递归的出口)
 * 3. 然后把所有的小规模的子问题的解，组合起来，得到要求解的大规模问题的解。(递归自动完成的)
 * 我们以后一旦想使用递归求解问题时,一定要往分解的思想上靠.
 *
 * 递归的优点:
 *      1.递归的代码往往简洁优雅
 *      2.递归分解的思想,很符合人类思考问题的方式,递归求解一般比较好想
 *
 * 递归的缺点:
 *      1.递归很危险,稍有不慎会栈溢出错误
 *      2.递归需要占用大量的栈内存空间,而且由于存在很多重复计算的部分,所以它的效率也很低
 *      总之就是时空复杂度都不优越
 *      既占内存,也不快
 * 但是递归虽然缺点很多,但递归仍然是比较常用的求解手段,因为它确实很好用
 *
 * @since 11:03
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorial(20));
        System.out.println(factorial2(20));
    }

    // 用递归求解
    public static long factorial2(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factorial2(n - 1);
    }

    // 使用循环求解n的阶乘
    public static long factorial(int n) {
        //  n! = n * (n-1) * (n-2) * ... * 1;
        long result = 1;
        int temp = n;
        // 有点不太好想循环的次数
        while (temp > 0) {
            result *= temp;
            temp--;
        }
        return result;
    }
}
